209. 长度最小的子数组

Similar Question

leading to the advanced question

Solution Tips

方案一: 滑动窗口

var minSubArrayLen = function(target, nums) {
    // 因为都是整数, 所以只需要动态的调整滑动窗口的大小就可以了
    // 小了就 end++, 大了就 start--
    // 依然是使用 sum 维护窗口即可

    let start = 0;
    let end = 0;
    let minLen = Number.MAX_SAFE_INTEGER;

    let sum = nums[0];

    while (end < nums.length) {
        if (sum < target) {
            end++;
            sum += nums[end];
        }
        else if (sum >= target) {
            minLen = Math.min(minLen, end - start);
            // start++ 这样 sum 一定变小, 下一轮就可以 end++ 继续遍历
            // end++ 一定是变大的, 所以没有意义
            sum -= nums[start];
            start++;
            // 只需要 minLen 就行, 不需要是最接近 target 的
            // 所以 > 也可以走这个分支
        }
    }
    if (start === 0) return 0;

    return minLen + 1;
};

方案二: 前缀和 + 二分查找

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int ans = Integer.MAX_VALUE;
        int[] sums = new int[n + 1]; 
        // 为了方便计算，令 size = n + 1 
        // sums[0] = 0 意味着前 0 个元素的前缀和为 0
        // sums[1] = A[0] 前 1 个元素的前缀和为 A[0]
        // 以此类推
        for (int i = 1; i <= n; i++) {
            sums[i] = sums[i - 1] + nums[i - 1];
        }
        for (int i = 1; i <= n; i++) {
            int target = s + sums[i - 1];
            int bound = Arrays.binarySearch(sums, target);
            if (bound < 0) {
                bound = -bound - 1;
            }
            if (bound <= n) {
                ans = Math.min(ans, bound - (i - 1));
            }
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}